This invention relates to techniques for determining location and, specifically, to techniques that utilize the NAVSTAR Global Positioning System (GPS).
The NAVSTAR Global Positioning System (GPS) developed by the United States Department of Defense uses a constellation of between 24 and 32 Medium Earth Orbit satellites that transmit precise microwave signals, which allows devices embodying GPS sensors to determine their current location. Initial applications were predominantly military; the first widespread consumer application was navigational assistance.
With the explosive growth in mobile communications devices, a new wave of location-based applications is emerging. These applications are characterized by a requirement for device-centered maps. One example is a form of “Yellow Pages” in which a map centered at the location of the mobile device presents user-selected establishments (e.g., barber shops) in situ. Another example would be an application enabling one to locate, on a device-centered map, members of his or her social network. In these applications, location involves but two dimensions (North/South and East/West). The ability of GPS to provide three dimensional locations (or “fixes”) is, for the most part, irrelevant. Accordingly, the narrative which follows ignores the three dimensional possibilities. Outdoors, GPS (using four or more satellites) is a reliable and accurate source of the location information essential to enable a device-centered map to be served across a network to a mobile device. However, today's GPS receivers operating in 3D mode (using four satellites) do not have the receive sensitivity required to generate fixes indoors. In 2D mode (using just three satellites and, most commonly, a pseudo satellite located at the center of the earth), the sensitivity improves slightly, but not enough. As a result, location-based applications utilize GPS outdoors, and any of several proprietary location service providers indoors.
Location services are built around proprietary databases, compiled by location service providers. These databases are essentially compilations of the locations of terrestrial transmitting towers (beacons), or compilations of the signal-strength contours surrounding these beacons, or compilations of the locations together with the associated signal-strength contours. A subscriber (to the location service) provides the ID's and (optionally) the associated signal strengths of any beacons detectable by his or her mobile device, and the location service provider responds with its best estimate of the location of the device.
FIG. 1 describes a typical Mobile Device Location System (MDLS) employed by a location service provider to compile its Beacon Location/Signal-Strength Contour Database (BLDB)—the database of beacon locations and associated signal-strength contours utilized in the servicing of subscriber requests. Key elements of this system (in addition to the aforementioned BLDB) are the Beacon Survey Database (BSDB), the Beacon Location/Signal-Strength Contour Engine (BLEN) and the Mobile Device Location Engine (MLEN). The Beacon Survey Database is comprised of measurements taken at various times and places for use by the BLEN in the compilation of the BLDB which, in turn, is used by MLEN to estimate the location of a subscriber's mobile device. As survey measurements are often taken within range of multiple beacons, it is necessary to demultiplex the measurement data for storage in BSDB, which is structured around beacons.
Whether the beacons are cellular towers or Wi-Fi access points—the measurement processes are largely identical. Measurements are taken using instruments similar to (and in some cases, identical to) the mobile communications devices the MDLS has been designed to locate. The standard mode of operation is to traverse the geography of interest with a measuring instrument, pausing periodically to record its location (using GPS) together with the ID's and signal-strengths of any beacons detectable by the device. As these measurements accumulate, beacon locations and associated signal-strength contours are generated and thereafter continually updated by the BLEN, to enable the generation of accurate and reliable estimates of location in response to subscriber requests. On the receipt of a request from a subscriber, the MLEN applies the information provided (by the subscriber) to generate its estimate of the subscriber's location. Methods for generating such estimates are well known in the art. One very simple approach would be to match the beacon presenting the strongest signal (as reported by the subscriber) with a beacon in the BLDB. Absent any signal-strength input, an approach might be to select from the beacons reported by the subscriber, the most frequently sensed, using a “sense count”, maintained by the MLEN and stored with each beacon in the BLDB.
The franchise of a location service provider may be valued in terms of its ability to reliably and accurately locate mobile devices. Because the techniques for estimating location and developing contours are understood and commonly practiced, the ability to reliably locate mobile devices hinges on the accuracy and comprehensiveness of the Beacon Survey Database. If the BSDB contains inaccurate measurements, those inaccuracies will result in inaccurate beacon locations or signal-strength contours in the BLDB, which will contribute to inaccuracy in the estimated location of a subscriber's mobile device. Moreover, if the BSDB is sparse, gaps in beacon and contour coverage are possible, rendering the service unreliable to its subscribers. To deliver reliable service thus requires complete and comprehensive coverage of the service domain.
The most common types of beacons in use today are cellular towers and Wi-Fi access points. While the former provide broader coverage in the aggregate, locating them with sufficient precision to enable accurate triangulation to a subscriber location requires a large number of measurements. Resigned to the requirement for a massive Beacon Survey Database, cell-tower-based service providers have, in some cases, opted to construct signal-strength contours as well, to mitigate the estimation error. Given the limited range of a Wi-Fi access point, access-point-based service providers take a different approach. With the acquisition of a handful of measurements for a given beacon, they may be able to estimate its location with sufficient accuracy to begin service immediately to subscribers within range of that beacon. However, there are many more Wi-Fi access points than cellular towers—and, to make matters worse, most are indoors, where the likelihood of three acquirable GPS satellites (required for a 2D GPS fix) is low.
While on the surface it might appear that cell-tower-based systems have the edge over access-point-based systems, some would argue that cell-tower-based systems are out of step with the growth in applications built on the assumption of broadband access, which in turn is fueling the rapid growth in Wi-Fi-only as well as dual-mode (cellular plus Wi-Fi) communications devices. As mobile broadband traffic searches for relief from the cost and congestion of the cellular networks, location-based applications will increasingly favor access-point-based location services. That is not to suggest that access point services will make cell tower services irrelevant; both will be needed.
Considering the limitations of current techniques for compiling large Beacon Survey Databases—there is clearly a need in the art for an MDLS framework to enable rapid, inexpensive compilation of comprehensive Beacon Survey Databases, with the accuracy required by current and contemplated location-based applications.